Digital filters, particularly FIR and IIR filters, are increasingly used in digital signal processing and real time digital and audio processing. As a result of the extensive use of these filters, powerful and mature optimization theories are available to aid in filter design. Conventional hardware realization of such filters utilizes the basic functional components of delay units, multipliers, and adders. Of these basic functional components, the hardware implementation of multipliers is typically the most complex and computationally expensive. In addition, multipliers occupy a significant portion of the available "real estate" on a given chip. Furthermore, substantial propagation delay is introduced by multipliers, thereby limiting processing speed.
In order to increase processing speed and simultaneously reduce component cost and complexity, contemporary filter design techniques often employ "multiplierless" technology, wherein the multipliers are replaced with binary adders and shift registers, and a "shift-and-add" scheme is employed in lieu of conventional multiplication techniques.
The use of multiplierless filtering requires that the coefficients by which the input data is multiplied comprise a sum of terms, each of the form 2.sup.p. This results from the fact that a binary multiplication by a "power-of-two" coefficient is equivalent to a shift of the multiplicand; complex multiplication may thus be effected through a series of simple shifting and adding operations.
Presently known multiplierless digital filters, however, are unsatisfactory in several respects. For example, coefficients expressed in terms of powers-of-two often contain terms of very high order, for example 2.sup.-28 and higher. In order to shift an n-bit input data term twenty-eight times, conventional shift registers must be of a length sufficient to accommodate at least n+28 bits. For an 18 bit input data value, this requires shift registers in excess of 46 bits in length, although a shorter length may suffice if truncation is permitted. Hardware implementation of these registers can be quite cumbersome, often introducing substantial propagation delay relative to lower order coefficient powers. In addition, the aggregate number of shifts for a coefficient having a plurality of higher order terms further decreases processing speed. See, for example, Bhattacharya et al. U.S. Pat. No. 4,782,458 issued Nov. 1, 1988; Owen et al. U.S. Pat. No. 4,356,588 issued Oct. 22, 1982; and Shah et al. U.S. Pat. No. 4,862,402 issued Aug. 29, 1989.
A multiplierless digital filter is needed which exploits the shift-and-add algorithm using sums of powers-of-two coefficients in a manner which optimizes the complexity of the shifter registers and the number of shifts required to "multiply" coefficients having high order exponential terms.